#include<stdio.h>
#include<malloc.h>

typedef struct node Node;

struct node{
	int data;
	Node *next;
};

int insertEnd(Node **, int);
int delete(Node *, int);

int checkPalindrome(Node *);
int checkPl(Node **, Node *);
Node *findMiddleNode(Node *);


int main(){
	Node *head = NULL;
	int i = 0;
	/*
	for(i = 1; i<=6; i++){
		insertEnd(&head, i);
	}*/
	
	insertEnd(&head, 1);
	insertEnd(&head, 3);
	insertEnd(&head, 0);
	insertEnd(&head, 7);
	insertEnd(&head, 7);
	insertEnd(&head, 0);
	insertEnd(&head, 3);
	insertEnd(&head, 1);
	
	debug(head);
	
	printf("\nThis is%sa Palindrome", (checkPalindrome(head))?" ":" not ");

	printf("\n--Palindrome Check ... Using Linked Lists\n");
	return 0;
}

int insertEnd(Node **head, int data){
	Node *newNode = (Node *)malloc(sizeof(Node));
	Node *thisNode = *head;
	
	newNode->data = data;
	newNode->next = NULL;
	
	if(!thisNode){
		*head = newNode;
		return 1;
	}
	while(thisNode->next){	//traverse until the end
		thisNode = thisNode->next;
	}
	thisNode->next = newNode;
	return 1;
}

int checkPalindrome(Node *head){
	Node *midNode;
	midNode = findMiddleNode(head);
	
	printf("\n--Palindrome Check--\n");
	
	printf("\nMiddleNode is: %d\n", midNode->data);
	
	printf("\n--Palindrome Check--\n");
	
	Node *newHead = head;
	
	return checkPl(&newHead, midNode->next);
}

int checkPl(Node **start, Node *mid){
	if(mid == NULL){
		return 1;
	}else if(checkPl(start, mid->next) && (*start)->data == mid->data){
			*start = (*start)->next;
			return 1;
	}else{
		return 0;
	}	
}

Node *findMiddleNode(Node *head){
	Node *thisNode = head, *doubleNode = head;
	int i = 0;
	while(doubleNode->next){
		if(i == 0){
			doubleNode = doubleNode->next;
			i = 1;
		}else if(i == 1){
			thisNode = thisNode->next;
			doubleNode = doubleNode->next;
			i = 0;
		}
	}
	return thisNode;
}

int debug(Node *head){
	printf("\n--DEBUG: Printing List");
	while(head){
		printf("\nValue: %d", head->data);
		head = head->next;
	}
	printf("\n--DEBUG: List Printed\n");
}
